SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

</head>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">For players of both rugby codes, see <a href="List_of_dual-code_rugby_internationals" title="List of dual-code rugby internationals">List of dual-code rugby internationals</a>.</div>

<p>In <a href="Coding_theory" title="Coding theory">coding theory</a>, the <b>dual code</b> of a <a href="Linear_code" title="Linear code">linear code</a>

</p>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C\subset \mathbb {F} _{q}^{n}}</annotation>

</semantics>

</math></span><img src="./5434a41e695ef583a79bf33cc4b3614b2949af16.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:7.504ex; height:3.176ex;" alt="{\displaystyle C\subset \mathbb {F} _{q}^{n}}" loading="lazy"></span></dd></dl>

<p>is the linear code defined by

</p>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C^{\perp }=\{x\in \mathbb {F} _{q}^{n}\mid \langle x,c\rangle =0\;\forall c\in C\}}</annotation>

</semantics>

</math></span><img src="./7a4dfad76b77b67a060a7ecc967e503d0465240c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:34.47ex; height:3.509ex;" alt="{\displaystyle C^{\perp }=\{x\in \mathbb {F} _{q}^{n}\mid \langle x,c\rangle =0\;\forall c\in C\}}" loading="lazy"></span></dd></dl>

<p>where

</p>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle x,c\rangle =\sum _{i=1}^{n}x_{i}c_{i}}</annotation>

</semantics>

</math></span><img src="./385997856bfe326e723d1265658f7d11ef0011d8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:15.956ex; height:6.843ex;" alt="{\displaystyle \langle x,c\rangle =\sum _{i=1}^{n}x_{i}c_{i}}" loading="lazy"></span></dd></dl>

<p>is a scalar product. In <a href="Linear_algebra" title="Linear algebra">linear algebra</a> terms, the dual code is the <a href="Annihilator_(ring_theory)" title="Annihilator (ring theory)">annihilator</a> of <i>C</i> with respect to the <a href="Bilinear_form" title="Bilinear form">bilinear form</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \langle \cdot \rangle }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle \cdot \rangle }</annotation>

</semantics>

</math></span><img src="./47e28d0cdb6d5e1c9af01324e09276f06e4d44c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.456ex; height:2.843ex;" alt="{\displaystyle \langle \cdot \rangle }" loading="lazy"></span>. The <a href="Dimension_(vector_space)" title="Dimension (vector space)">dimension</a> of <i>C</i> and its dual always add up to the length <i>n</i>:

</p>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \dim C+\dim C^{\perp }=n.}</annotation>

</semantics>

</math></span><img src="./2bfec3a64944e03c2633bfdefcdc25abb7cec47b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:21.58ex; height:2.843ex;" alt="{\displaystyle \dim C+\dim C^{\perp }=n.}" loading="lazy"></span></dd></dl>

<p>A <a href="Generator_matrix" title="Generator matrix">generator matrix</a> for the dual code is the <a href="Parity-check_matrix" title="Parity-check matrix">parity-check matrix</a> for the original code and vice versa. The dual of the dual code is always the original code.

</p>

<div class="mw-heading mw-heading2"><h2 id="Self-dual_codes">Self-dual codes</h2></div>

<p>A <b>self-dual code</b> is one which is its own dual. This implies that <i>n</i> is even and dim <i>C</i> = <i>n</i>/2. If a self-dual code is such that each codeword's weight is a multiple of some constant <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c>1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c>1}</annotation>

</semantics>

</math></span><img src="./bd1d6b5c226641ad3def8e65631f0eb463d9c67a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;" alt="{\displaystyle c>1}" loading="lazy"></span>, then it is of one of the following four types:<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><b>Type I</b> codes are binary self-dual codes which are not <a href="Doubly_even_code" class="mw-redirect" title="Doubly even code">doubly even</a>. Type I codes are always <a href="Even_code" title="Even code">even</a> (every codeword has even <a href="Hamming_weight" title="Hamming weight">Hamming weight</a>).</li>

<li><b>Type II</b> codes are binary self-dual codes which are doubly even.</li>

<li><b>Type III</b> codes are ternary self-dual codes. Every codeword in a Type III code has Hamming weight divisible by 3.</li>

<li><b>Type IV</b> codes are self-dual codes over <b>F</b><sub>4</sub>. These are again even.</li></ul>

<p>Codes of types I, II, III, or IV exist only if the length <i>n</i> is a multiple of 2, 8, 4, or 2 respectively.

</p><p>If a self-dual code has a generator matrix of the form <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=[I_{k}|A]}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=[I_{k}|A]}</annotation>

</semantics>

</math></span><img src="./40cbb03fc36f521700039290c18e93e50425d870.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.721ex; height:2.843ex;" alt="{\displaystyle G=[I_{k}|A]}" loading="lazy"></span>, then the dual code <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C^{\perp }}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C^{\perp }}</annotation>

</semantics>

</math></span><img src="./d2329fab4b0d3cf8941ef7197caf13ef920270b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.309ex; height:2.676ex;" alt="{\displaystyle C^{\perp }}" loading="lazy"></span> has <a href="Generator_matrix" title="Generator matrix">generator matrix</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [-{\bar {A}}^{T}|I_{k}]}">

<msup>

<mover>

</mover>

</mrow>

</mrow>

</msup>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [-{\bar {A}}^{T}|I_{k}]}</annotation>

</semantics>

</math></span><img src="./ec3892999ba6b47f4c8757c5a098d087ff9c2514.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.025ex; height:3.676ex;" alt="{\displaystyle [-{\bar {A}}^{T}|I_{k}]}" loading="lazy"></span>, where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle I_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I_{k}}</annotation>

</semantics>

</math></span><img src="./d658e7f6b34dd1d3025a7c9a72efba5b9f46475d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.112ex; height:2.509ex;" alt="{\displaystyle I_{k}}" loading="lazy"></span> is the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n/2)\times (n/2)}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n/2)\times (n/2)}</annotation>

</semantics>

</math></span><img src="./7f32e22ab8fca8d2454e2388e65627da328690e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.898ex; height:2.843ex;" alt="{\displaystyle (n/2)\times (n/2)}" loading="lazy"></span> identity matrix and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\bar {a}}=a^{q}\in \mathbb {F} _{q}}">

<mover>

</mover>

</mrow>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\bar {a}}=a^{q}\in \mathbb {F} _{q}}</annotation>

</semantics>

</math></span><img src="./283b69e14203adedcc9981f0c802dd9402374220.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.796ex; height:3.009ex;" alt="{\displaystyle {\bar {a}}=a^{q}\in \mathbb {F} _{q}}" loading="lazy"></span>.

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFConwaySloane,_N.J.A.1988" class="citation book cs1"><a href="John_Horton_Conway" title="John Horton Conway">Conway, J.H.</a>; <a href="Neil_Sloane" title="Neil Sloane">Sloane, N.J.A.</a> (1988). <a rel="nofollow" class="external text" href="https://archive.org/details/spherepackingsla0000conw/page/77"><i>Sphere packings, lattices and groups</i></a>. Grundlehren der mathematischen Wissenschaften. Vol. 290. <a href="Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a>. p. <a rel="nofollow" class="external text" href="https://archive.org/details/spherepackingsla0000conw/page/77">77</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-96617-X</bdi>.</cite></span>

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin" style="">

<ul><li><cite id="CITEREFHill1986" class="citation book cs1">Hill, Raymond (1986). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/firstcourseincod0000hill"><i>A first course in coding theory</i></a></span>. Oxford Applied Mathematics and Computing Science Series. <a href="Oxford_University_Press" title="Oxford University Press">Oxford University Press</a>. p. <a rel="nofollow" class="external text" href="https://archive.org/details/firstcourseincod0000hill/page/67">67</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-19-853803-0</bdi>.</cite></li>

<li><cite id="CITEREFPless1982" class="citation book cs1"><a href="Vera_Pless" title="Vera Pless">Pless, Vera</a> (1982). <a href="Introduction_to_the_Theory_of_Error-Correcting_Codes" title="Introduction to the Theory of Error-Correcting Codes"><i>Introduction to the theory of error-correcting codes</i></a>. Wiley-Interscience Series in Discrete Mathematics. <a href="John_Wiley_%26_Sons" class="mw-redirect" title="John Wiley & Sons">John Wiley & Sons</a>. p. 8. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-471-08684-3</bdi>.</cite></li>

<li><cite id="CITEREFJ.H._van_Lint1992" class="citation book cs1">J.H. van Lint (1992). <a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoco0000lint/page/34"><i>Introduction to Coding Theory</i></a>. <a href="Graduate_Texts_in_Mathematics" title="Graduate Texts in Mathematics">GTM</a>. Vol. 86 (2nd ed.). Springer-Verlag. p. <a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoco0000lint/page/34">34</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-54894-7</bdi>.</cite></li></ul>

</div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20170516194659/https://www.maths.manchester.ac.uk/~pas/code/notes/part9.pdf">MATH32031: Coding Theory - Dual Code</a> - pdf with some examples and explanations</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-03-10" href="https://en.wikipedia.org/wiki/?title=Dual_code&oldid=1212907100">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>